package practice;

import java.util.*;

public class Day47 {

    public static void main(String[] args) {

    }
    public String minWindow(String s, String t) {
        Map<Character,Integer> sMap = new HashMap<>();
        Map<Character,Integer> tMap = new HashMap<>();
        for(char ch : t.toCharArray()) {
            tMap.put(ch,tMap.getOrDefault(ch,0)+1);
        }
        int min = Integer.MAX_VALUE;
        int retL = -1;
        int retR = -1;
        int left = 0;
        int right = 0;
        int count = 0;
        while(right < s.length()) {
            sMap.put(s.charAt(right),sMap.getOrDefault(s.charAt(right),0)+1);
            if(sMap.getOrDefault(s.charAt(right),0) <= tMap.getOrDefault(s.charAt(right),0)) {
                count++;
            }
            while(count >= t.length()) {
                if(min > right-left+1) {
                    min = right-left+1;
                    retL = left;
                    retR = right;
                }
                sMap.put(s.charAt(left),sMap.getOrDefault(s.charAt(left),0)-1);
                if(sMap.getOrDefault(s.charAt(left),0) < tMap.getOrDefault(s.charAt(left),0)) {
                    count--;
                }
                left++;
            }
            right++;
        }
        if(retL == -1 || retR == -1) {
            return "";
        }
        return s.substring(retL,retR+1);
    }
    public int[] sortArray(int[] nums) {
        //快排
        int n = nums.length;
        sortArrayChild(nums,0,n-1);
        return nums;
    }
    private void sortArrayChild(int[] nums, int left, int right) {
        if(left >= right) {
            return;
        }
        //取随机数
        Random random = new Random();
        int key = nums[random.nextInt(right-left+1) + left];
        int i = left;
        int start = left-1;
        int end = right+1;
        while(i < end) {
            if(nums[i] < key) {
                swap(nums,i++,++start);
            }else if(nums[i] > key) {
                swap(nums,i,--end);
            }else {
                i++;
            }
        }
        sortArrayChild(nums,left,start);
        sortArrayChild(nums,end,right);

    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;

    }
    class LRUCache {

        class Node{
            Node prev;
            Node next;
            int val;
            int key;
            public Node(int key,int val) {
                this.val = val;
                this.key = key;
            }
            public Node() {}
        }
        Node head;
        Node tail;
        Map<Integer,Node> map;
        int n;
        int count;
        public LRUCache(int capacity) {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
            map = new HashMap<>();
            n = capacity;
        }

        public int get(int key) {
            Node node = map.getOrDefault(key,null);
            if(node == null) {
                return -1;
            }else {
                moveToHead(node);
                return node.val;
            }
        }

        public void put(int key, int value) {
            Node node = map.getOrDefault(key,null);
            if(node == null) {
                Node newNode = new Node(key,value);
                map.put(key,newNode);
                addToHead(newNode);
                count++;
                if(count > n) {
                    //
                    Node del = tail.prev;
                    removeNode(del);
                    map.remove(del.key);
                    count--;
                }
            }else {
                moveToHead(node);
                map.get(key).val = value;
            }
        }
        private void addToHead(Node node) {
            head.next.prev = node;
            node.next = head.next;
            head.next = node;
            node.prev = head;
        }
        private void removeNode(Node node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }
        private void moveToHead(Node node) {
            removeNode(node);
            addToHead(node);
        }
    }
    int m;
    int n;
    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(dfs(board,word,1,i,j)) {
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board,String s,int total,int i,int j) {
        if(i < 0 || i >= m || j < 0 || j >= n || board[i][j] != s.charAt(total-1)) {
            return false;
        }
        if(total >= s.length()) {
            return true;
        }
        board[i][j] = ' ';
        boolean flag = dfs(board,s,total+1,i,j+1) || dfs(board,s,total+1,i+1,j) || dfs(board,s,total+1,i-1,j) || dfs(board,s,total+1,i,j-1);
        board[i][j] = s.charAt(total-1);
        return flag;
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        return (dfs(nums1,0,nums1.length-1,nums2,0,nums2.length-1,(n+m+1)/2) + dfs(nums1,0,nums1.length-1,nums2,0,nums2.length-1,(n+m+2)/2)) * 0.5;
    }
    private double dfs(int[] nums1,int s1,int e1,int[] nums2,int s2,int e2,int k) {
        //保证nums1是长的
        if(e1-s1+1 < e2-s2+1) {
            return dfs(nums2,s2,e2,nums1,s1,e1,k);
        }
        if(e2-s2+1 == 0) {
            return nums1[k+s1-1];
        }
        if(k == 1) {
            return Math.min(nums1[s1],nums2[s2]);
        }

        int i = Math.min(e1-s1+1,k/2) + s1-1;
        int j = Math.min(e2-s2+1,k/2) + s2-1;
        if(nums1[i] < nums2[j]) {
            //抛弃掉nums1中i位置之前的所有元素
            return dfs(nums1,i+1,e1,nums2,s2,e2,k-(i-s1+1));
        }else {
            //抛弃掉nums2中j位置之前的所有元素
            return dfs(nums1,s1,e1,nums2,j+1,e2,k-(j-s2+1));
        }
    }

    public int kthSmallest(TreeNode root, int k) {
        //利用中序遍历是有序地=>寻找中序遍历后的数组中的第k大元素
        //左中右
        TreeNode cur = root;
        TreeNode prev = cur;
        TreeNode flag = null;
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        while(cur != null || !s.isEmpty()) {
            while(cur != null) {
                s.push(cur);
                cur = cur.left;
            }
            TreeNode top = s.pop();
            list.add(top.val);
            if(top.right != null) {
                cur = top.right;
            }
        }
        return root == null ? 0 : list.get(k-1);

    }

    private void swap(int[] arr,int a,int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int i = 0;
        while(i < n) {
            while(nums[i] > 0 && nums[i]-1 < n && nums[i] != nums[nums[i]-1]) {
                swap(nums,i,nums[i]-1);
            }
            i++;
        }
        for(int j = 0; j < n; j++) {
            if(j+1 != nums[j]) {
                return j+1;
            }
        }
        return n+1;
    }

    class LRUCache1 extends LinkedHashMap<Integer,Integer>{

        int n;
        public LRUCache1(int capacity) {
            super(capacity,0.75F,true);
            this.n = capacity;
        }
        // LRUCache map;

        @Override
        public boolean removeEldestEntry(Map.Entry eld) {
            return size() > n;
        }

        public int get(int key) {
            return super.getOrDefault(key,-1);
        }

        public void put(int key, int value) {
            super.put(key,value);
        }
    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        int m = prerequisites.length;
        Map<Integer,List<Integer>> map = new HashMap<>();
        //建图和统计入度
        for(int i = 0; i < m; i++) {
            in[prerequisites[i][0]]++;
            if(map.getOrDefault(prerequisites[i][1],null) == null) {
                map.put(prerequisites[i][1],new LinkedList<>());
            }
            map.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            int top = queue.poll();

            for(int k : map.getOrDefault(top,new LinkedList<>())) {
                in[k]--;
                if(in[k] == 0) {
                    queue.offer(k);
                }
            }
        }
        for(int x : in) {
            System.out.println("x: " + x);
            if(x != 0) {
                return false;
            }
        }
        return true;

    }
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new LinkedList<>();

        Map<Character,Integer> sMap = new HashMap<>();
        Map<Character,Integer> pMap = new HashMap<>();

        for(char ch : p.toCharArray()) {
            pMap.put(ch,pMap.getOrDefault(ch,0)+1);
        }
        int count = 0;
        int plen = p.length();
        int i = 0;
        int j = 0;
        while(i < s.length()) {
            sMap.put(s.charAt(i),sMap.getOrDefault(s.charAt(i),0)+1);
            if(sMap.getOrDefault(s.charAt(i),0) <= pMap.getOrDefault(s.charAt(i),0)) {
                count++;
            }
            while(sMap.getOrDefault(s.charAt(i),0) > pMap.getOrDefault(s.charAt(i),0)) {
                sMap.put(s.charAt(j),sMap.getOrDefault(s.charAt(j),0)-1);
                if(sMap.getOrDefault(s.charAt(j),0) < pMap.getOrDefault(s.charAt(j),0)) {
                    count--;
                }
                j++;
            }
            if(count == plen) {
                list.add(j);
            }
            i++;
        }
        return list;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode slow = newHead;
        ListNode fast = newHead;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        System.out.println("222222");
        //slow此时为中点
        ListNode slowNext = slow.next;
        while(slowNext != null) {
            ListNode nx = slowNext.next;
            slowNext.next = slow;
            slow = slowNext;
            slowNext = nx;
        }
        fast = newHead.next;
        System.out.println("11111");
        while(fast != slow) {
            if(fast.val != slow.val) {
                return false;
            }
            if(slow.next == fast) {
                return true;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
    public int maxArea(int[] height) {
        int left = 0;
        int n = height.length;
        int right = n-1;
        int max = 0;
        while(left < right) {
            max = Math.max(max,Math.min(height[left],height[right]) * (right-left));
            if(height[left] < height[right]) {
                left++;
            }else{
                right--;
            }
        }
        return max;
    }
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int i = 0;
        while(i < n) {
            while(nums[i] > 0 && nums[i]-1 < n && nums[i] != nums[nums[i]-1]) {
                swap(nums,i,nums[i]-1);
            }
            i++;
        }
        for(int j = 0; j < n; j++) {
            if(j+1 != nums[j]) {
                return j+1;
            }
        }
        return n+1;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = new ListNode();
        start.next = head;
        ListNode end = start;
        ListNode prev = start;
        while(end != null) {
            for(int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if(end == null) {
                return start.next;
            }
            ListNode temp = prev.next;
            ListNode endN = end.next;
            end.next = null;
            prev.next = reverse(temp);
            temp.next = endN;
            prev = temp;
            end = temp;
        }
        return start.next;
    }
    private ListNode reverse(ListNode node) {
        ListNode cur = null;
        ListNode newHead = new ListNode(0);
        while(node != null) {
            ListNode nodeN = node.next;
            node.next = cur;
            newHead.next = node;
            cur = node;
            node = nodeN;
        }
        return newHead.next;
    }
    public int search(int[] nums, int target) {
        int left = 0;
        int n = nums.length;
        int right  = n-1;
        while(left <= right) {

            int mid = left + (right-left)/2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] > nums[left]) {
                if(nums[mid] >= target && target >= nums[left]) {
                    right = mid-1;
                }else {
                    left = mid+1;
                }
            }else {
                if(nums[right] >= target && target >= nums[mid]) {
                    left = mid + 1;
                }else {
                    right = mid-1;
                }
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    int pos = 0;
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int left,int right) {
        if(left > right) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[pos]);
        int index = findIndex(preorder,inorder,left,right);
        root.left = buildTreeChild(preorder,inorder,left,index-1);
        root.right = buildTreeChild(preorder,inorder,index+1,right);
        return root;
    }
    private int findIndex(int[] preorder,int[] inorder, int left,int right) {
        for(int i = left; i <= right; i++) {
            if(inorder[i] == preorder[pos]) {
                pos++;
                return i;
            }
        }
        return -1;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if(root == q || root == p) {
            return root;
        }

        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree == null) {
            return leftTree;
        }
        if(leftTree == null && rightTree != null) {
            return rightTree;
        }
        if(leftTree != null && rightTree != null) {
            return root;
        }
        return null;
    }

    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int n = temperatures.length;
        int[] ret = new int[n];
        for(int i = 0; i < n; i++) {
            if(stack.isEmpty()) {
                stack.push(i);
            }else {
                if(temperatures[stack.peek()] >= temperatures[i]) {
                    stack.push(i);
                }else {
                    while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                        int top = stack.pop();
                        ret[top] = i-top;
                    }
                    stack.push(i);

                }
            }
        }
        return ret;
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ret = new int[n-k+1];
        int left = 0;
        int right = 0;
        Deque<Integer> queue = new LinkedList<>();
        int i = 0;
        for(i = 0; i < k; i++) {
            while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
        }
        ret[0] = queue.peekFirst();

        for(; i < n; i++) {
            if(queue.peekFirst() == nums[i-k]) {
                queue.removeFirst();
            }
            while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
            ret[i-k+1] = queue.peekFirst();
        }
        return ret;
    }

    public String minWindow(String s, String t) {
        Map<Character,Integer> sMap = new HashMap<>();
        Map<Character,Integer> tMap = new HashMap<>();
        for(char ch : t.toCharArray()) {
            tMap.put(ch,tMap.getOrDefault(ch,0)+1);
        }
        int retL = -1;
        int retR = -1;
        int min = Integer.MAX_VALUE;
        int count = 0;
        int tLen = t.length();
        int left = 0;
        int right = 0;
        while(right < s.length()) {
            sMap.put(s.charAt(right),sMap.getOrDefault(s.charAt(right),0)+1);
            if(sMap.getOrDefault(s.charAt(right),0) <= tMap.getOrDefault(s.charAt(right),0)) {
                count++;
            }
            while(count >= tLen) {
                if(min > right-left+1) {
                    min = right-left+1;
                    retL = left;
                    retR = right;
                }
                sMap.put(s.charAt(left),sMap.getOrDefault(s.charAt(left),0)-1);
                if(sMap.getOrDefault(s.charAt(left),0) < tMap.getOrDefault(s.charAt(left),0)) {
                    count--;
                }
                left++;
            }
            right++;
        }
        if(retL == -1 || retR == -1) {
            return "";
        }
        return s.substring(retL,retR+1);
    }

    private void swap(int[] arr,int a,int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int i = 0;
        while(i < n) {
            while(nums[i] > 0 && nums[i]-1 < n && nums[i] != nums[nums[i]-1]) {
                swap(nums,i,nums[i]-1);
            }
            i++;
        }
        for(int j = 0; j < n; j++) {
            if(j+1 != nums[j]) {
                return j+1;
            }
        }
        return n+1;

    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        Queue<int[]> queue = new PriorityQueue<>((o1,o2)->{
            //大根堆
            return o1[0]-o2[0] >= 0 ? -1 : 1;
        });
        int right = 0;
        for(right = 0; right < k; right++) {
            queue.offer(new int[]{nums[right],right});
        }
        int left = 0;
        List<Integer> list = new ArrayList<>();
        list.add(queue.peek()[0]);
        while(right < nums.length) {
            queue.offer(new int[]{nums[right],right});
            while(queue.peek()[1] <= right-k) {
                //当前最大元素已经不在窗口内了
                queue.poll();
            }
            list.add(queue.peek()[0]);
            right++;
        }
        int i = 0;
        int[] ret = new int[list.size()];
        for(int x : list) {
            ret[i++] = x;
        }
        return ret;
    }
    public ListNode swapPairs(ListNode root) {
        if(root == null || root.next == null) {
            return root;
        }
        ListNode cur = root.next;
        root.next = swapPairs(cur.next);
        cur.next = root;
        return cur;
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode cur = newHead;
        ListNode prev = null;
        for(int i = 0; i < n; i++) {
            cur = cur.next;
        }

        ListNode find = newHead;
        while(cur != null) {
            prev = find;
            find = find.next;
            cur = cur.next;
        }
        if(find != null) {
            prev.next = find.next;
        }
        return newHead.next;
    }
    class Node{
        Node prev;
        Node next;
        int val;
        int key;
        public Node(){}
        public Node(int key,int val) {
            this.val = val;
            this.key = key;
        }
    }
    Node head;
    Node tail;
    int n;
    int count;
    Map<Integer,Node> map;
    public LRUCache(int capacity) {
        head = new Node();
        tail = new Node();
        map = new HashMap<>();
        head.next = tail;
        tail.prev = head;
        this.n = capacity;
    }

    public int get(int key) {
        Node node = map.getOrDefault(key,null);
        if(node == null) {
            return -1;
        }else {
            moveToHead(node);
            return node.val;
        }
    }

    public void put(int key, int value) {
        Node node = map.getOrDefault(key,null);
        if(node == null) {
            Node newNode = new Node(key,value);
            map.put(key,newNode);
            addToHead(newNode);
            count++;
            if(n < count) {
                Node cur = tail.prev;
                removeNode(cur);
                map.remove(cur.key);
                count--;
            }
        }else {
            node.val = value;
            moveToHead(node);
        }
    }
    private void addToHead(Node node) {
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }
    private void removeNode(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    int n;
    List<List<String>> ret = new LinkedList<>();
    List<String> list = new LinkedList<>();
    public List<List<String>> partition(String s) {
        n = s.length();
        dfs(s,0,0);
        return ret;
    }
    private void dfs(String s, int left,int right) {
        if(right >= n) {
            ret.add(new LinkedList(list));
            return;
        }
        if(right < n-1) {
            dfs(s,left,right+1);
        }
        if(isVaild(s,left,right)) {
            list.add(s.substring(left,right+1));
            dfs(s,right+1,right+1);
            list.remove(list.size()-1);
        }


    }
    private boolean isVaild(String s, int left,int right) {
        while(left < right) {
            if(s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    class Node{
        boolean flag;
        Node[] nodes  = new Node[27];
    }
    Node head = new Node();
    public Trie() {
        head = new Node();
    }

    public void insert(String word) {
        Node cur = head;
        for(char c : word.toCharArray()) {
            Node node = new Node();
            if(null == cur.nodes[c-'a']) {
                cur.nodes[c-'a'] = node;
            }
            cur = cur.nodes[c-'a'];
        }
        cur.flag = true;
    }

    public boolean search(String word) {
        Node cur = head;
        for(char c : word.toCharArray()) {
            if(cur.nodes[c-'a'] == null) {
                return false;
            }
            cur = cur.nodes[c-'a'];

        }
        return  cur.flag;
    }

    public boolean startsWith(String prefix) {
        Node cur = head;
        for(char c : prefix.toCharArray()) {
            if(cur.nodes[c-'a'] == null) {
                return false;
            }
            cur = cur.nodes[c-'a'];
        }
        return true;
    }

    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder ret = new StringBuilder();
        //从前往后放
        for(char ch : s.toCharArray()) {
            //一旦遇到]就停止，往前处理数据
            if(ch != ']') {
                stack.push(ch);
            } else {
                StringBuilder str = new StringBuilder();
                while(!stack.isEmpty() && !Character.isDigit(stack.peek())) {
                    if(Character.isLetter(stack.peek())) {
                        str.append(stack.pop());
                    }else {
                        stack.pop();
                    }
                }
                //接下来是对数字进行处理，有可能为几十，几百
                int sum = 0;
                int k = 0;
                while(!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    sum += ((stack.pop()-'0') * Math.pow(10,k++));
                }
                str = str.reverse();
                while(sum != 0) {
                    for(char c : str.toString().toCharArray()) {
                        stack.push(c);
                    }
                    sum--;
                }

            }

        }
        while(!stack.isEmpty()) {
            ret.append(stack.pop());
        }
        return ret.reverse().toString();
    }
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ret = new LinkedList<>();
        int i = 0;
        int j = 0;
        int top = matrix.length-1;
        int bottom = matrix[0].length-1;
        while(i <= top && j <= bottom) {
            for(int k = j; k <= bottom; k++) {
                ret.add(matrix[i][k]);
            }

            for(int k = i+1; k <= top; k++) {
                ret.add(matrix[k][bottom]);
            }
            if(j != bottom && i != top) {
                for(int k = bottom-1; k >= j; k--) {
                    ret.add(matrix[top][k]);
                }
                for(int k = top-1; k >= i+1; k--) {
                    ret.add(matrix[k][j]);
                }
            }
            i++;
            j++;
            top--;
            bottom--;
        }
        return ret;

    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int pos = 0;
        int[] dp = new int[n+1];
        for(int x : nums) {
            if(pos == 0 || x > dp[pos]) {
                dp[++pos] = x;
            }else {
                //二分查找出最佳位置
                int left = 1;
                int right = pos;
                while(left < right) {
                    int mid = (right-left)/2 + left;
                    if(dp[mid] < x) {
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                dp[left] = x;
            }

        }
        return pos;
    }

    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n-1;
        while(left < right) {
            int mid = left + (right-left)/2;
            if(nums[mid] >= nums[left]) {
                if(target >= nums[left] && target <= nums[mid]) {
                    right = mid;
                }else {
                    left = mid+1;
                }
            }else {
                if(target <= nums[right] && target >= nums[mid]) {
                    left = mid;
                }else {
                    right = mid-1;
                }
            }
        }
        return nums[left] == target ? left : -1;
    }

    class MedianFinder {

        //大根堆，A中的元素都要比B中的小
        PriorityQueue<Integer> A;

        //小根堆，其中所有元素都要比大根堆中大
        PriorityQueue<Integer> B;
        public MedianFinder() {
            A = new PriorityQueue<>((o1,o2)->{
                return o2.compareTo(o1);
            });
            B = new PriorityQueue<>();
        }

        public void addNum(int num) {
            if(A.size() == B.size()) {
                B.offer(num);
                A.offer(B.poll());
            }else if(A.size() == B.size() + 1){
                A.offer(num);
                B.offer(A.poll());
            }
        }

        public double findMedian() {
            if(A.size() == B.size()) {
                return (A.peek() + B.peek()) / 2.0;
            }else if(A.size() == B.size() + 1) {
                return A.peek();
            }
            return 0;
        }
    }

    public int maxProduct(int[] nums) {
        int n = nums.length;
        //f[i]表示以i位置为结尾的最大乘积子数组
        int[] f = new int[n+1];
        //g[i]表示以i位置为结尾的最小乘积子数组
        int[] g = new int[n+1];
        f[0] = 1;
        g[0] = 1;
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            if(nums[i-1] < 0) {
                f[i] = Math.max(nums[i-1],g[i-1]*nums[i-1]);
                g[i] = Math.min(nums[i-1],f[i-1] * nums[i-1]);
            }else {
                f[i] = Math.max(nums[i-1],f[i-1] * nums[i-1]);
                g[i] = Math.min(nums[i-1],g[i-1] * nums[i-1]);
            }
            max = Math.max(f[i],max);
        }
        return max;

    }

    public int trap(int[] height) {
        //求左边最高和右边最高，然后最后两边的较小值减去当前位置的高度，即是当前位置所能接的最多的雨水
        int n = height.length;
        int[] left = new int[n+1];
        int[] right = new int[n+1];
        for(int i = 1; i <= n; i++) {
            left[i] = Math.max(height[i-1],left[i-1]);
        }
        for(int i = n-1; i >= 0; i--) {
            right[i] = Math.max(right[i+1],height[i]);
        }
        int count = 0;
        for(int i = 1; i <= n; i++) {
            count += (Math.max(0,Math.min(left[i],right[i])-height[i-1]));
        }
        return count;
    }
    public int trap(int[] height) {
        //求左边最高和右边最高，然后最后两边的较小值减去当前位置的高度，即是当前位置所能接的最多的雨水
        int n = height.length;
        int[] left = new int[n+1];
        int[] right = new int[n+1];
        for(int i = 1; i <= n; i++) {
            left[i] = Math.max(height[i-1],left[i-1]);
        }
        for(int i = n-1; i >= 0; i--) {
            right[i] = Math.max(right[i+1],height[i]);
        }
        int count = 0;
        for(int i = 1; i <= n; i++) {
            count += (Math.max(0,Math.min(left[i],right[i])-height[i-1]));
        }
        return count;
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ret = new int[n-k+1];
        int left = 0;
        int right = 0;
        Deque<Integer> queue = new LinkedList<>();
        int i = 0;
        for(i = 0; i < k; i++) {
            while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
        }
        ret[0] = queue.peekFirst();

        for(; i < n; i++) {
            if(queue.peekFirst() == nums[i-k]) {
                queue.removeFirst();
            }
            while(!queue.isEmpty() && queue.peekLast() < nums[i]) {
                queue.removeLast();
            }
            queue.addLast(nums[i]);
            ret[i-k+1] = queue.peekFirst();
        }
        return ret;
    }

    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        int sum = 1;
        ret[0] = 1;
        for(int i = 1; i < n; i++) {
            ret[i] = ret[i-1] * nums[i-1];
        }
        for(int i = n-2; i >= 0; i--) {
            sum *= nums[i+1];
            ret[i] *= sum;
        }
        return ret;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] in = new int[numCourses];
        int m = prerequisites.length;
        Map<Integer,List<Integer>> map = new HashMap<>();
        //建图和统计入度
        for(int i = 0; i < m; i++) {
            in[prerequisites[i][0]]++;
            if(map.getOrDefault(prerequisites[i][1],null) == null) {
                map.put(prerequisites[i][1],new LinkedList<>());
            }
            map.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            int top = queue.poll();

            for(int k : map.getOrDefault(top,new LinkedList<>())) {
                in[k]--;
                if(in[k] == 0) {
                    queue.offer(k);
                }
            }
        }
        for(int x : in) {
            System.out.println("x: " + x);
            if(x != 0) {
                return false;
            }
        }
        return true;

    }

    public int subarraySum(int[] nums, int k) {
        //前缀和
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int sum = 0;
        int count = 0;
        for(int x : nums) {
            sum += x;
            count += map.getOrDefault(sum-k,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return count;

    }

    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int x : nums) {
            set.add(x);
        }
        int max = 0;
        for(int x : set) {
            int count = 1;
            if(!set.contains(x-1)) {
                int cur = x;
                while(set.contains(cur+1)) {
                    count++;
                    cur++;
                }
                max = Math.max(max,count);
            }
        }
        return max;
    }

    public boolean isPalindrome(ListNode head) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode slow = newHead;
        ListNode fast = newHead;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        System.out.println("222222");
        //slow此时为中点
        ListNode slowNext = slow.next;
        while(slowNext != null) {
            ListNode nx = slowNext.next;
            slowNext.next = slow;
            slow = slowNext;
            slowNext = nx;
        }
        fast = newHead.next;
        System.out.println("11111");
        while(fast != slow) {
            if(fast.val != slow.val) {
                return false;
            }
            if(slow.next == fast) {
                return true;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((node1,node2)->{
            return node1.val - node2.val >= 0 ? 1 : -1;
        });
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        for(ListNode node : lists) {
            if(node != null) {
                queue.offer(node);
            }
        }
        while(!queue.isEmpty()) {
            ListNode top = queue.poll();
            cur.next = top;
            cur = cur.next;
            if(top.next != null) {
                queue.offer(top.next);
            }
        }
        return newHead.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode start = newHead;
        ListNode end = newHead;

        while(end != null) {
            for(int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if(end == null) {
                return newHead.next;
            }
            ListNode prev = start.next;
            ListNode endNext = end.next;
            end.next = null;
            start.next = reverse(prev);
            prev.next = endNext;
            start = prev;
            end = start;
        }
        return newHead.next;
    }
    private ListNode reverse(ListNode node) {
        ListNode newHead = new ListNode(0);
        ListNode cur = null;
        while(node != null) {
            ListNode nodeNext = node.next;
            newHead.next = node;
            node.next = cur;
            cur = node;
            node = nodeNext;

        }
        return newHead.next;
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        int k = 0;
        ListNode newHead = new ListNode();
        ListNode cur = newHead;
        while(cur1 != null && cur2 != null) {
            int sum = cur1.val + cur2.val + k;
            cur.next = new ListNode(sum % 10);
            k = sum / 10;;
            cur1 = cur1.next;
            cur2 = cur2.next;
            cur = cur.next;
        }
        while(cur1 != null) {
            cur.next = new ListNode((cur1.val+k) % 10);
            k = (cur1.val+k) / 10;
            cur1 = cur1.next;
            cur = cur.next;
        }

        while(cur2 != null) {
            cur.next = new ListNode((cur2.val+k) % 10);
            k = (cur2.val+k) / 10;
            cur2 = cur2.next;
            cur = cur.next;
        }
        if(k != 0) {
            cur.next = new ListNode(k);
        }

        return newHead.next;
    }

    private void swap(int[] nums,int a,int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int i = 0;
        while(i < n) {
            while(i < n && nums[i] >= 1 && nums[i]-1 < n && nums[i] != nums[nums[i]-1]) {
                swap(nums,i,nums[i]-1);
            }
            i++;
        }
        for(int j = 0; j < n; j++) {
            if(nums[j] != j+1) {
                return j+1;
            }
        }
        return n+1;
    }

    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int x : nums) {
            set.add(x);
        }
        int max = 0;
        for(int x : set) {
            int count = 1;
            if(!set.contains(x-1)) {
                int cur = x;
                while(set.contains(cur+1)) {
                    count++;
                    cur++;
                }
                max = Math.max(max,count);
            }
        }
        return max;
    }
}
